/*
 * @lc app=leetcode.cn id=16 lang=csharp
 *
 * [16] 最接近的三数之和
 */

// @lc code=start
public class Solution {
    public int ThreeSumClosest(int[] nums, int target) {
        Array.Sort(nums);

        int closestSum = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < nums.Length - 2; i++)
        {
            if (i > 0 && nums[i] == nums[i - 1])
            {
                continue;
            }
            
            var sum = nums[i] + nums[^1] + nums[^2];
            if (sum < target )
            {
                if (target - sum < Math.Abs(closestSum - target))
                {
                    closestSum = sum;
                }
                continue;
            }
            
            sum = nums[i] + nums[i+1] + nums[i+2];
            if (sum > target )
            {
                if ((sum - target) < Math.Abs(closestSum - target))
                {
                    closestSum = sum;
                }
                break;
            }
            int left = i + 1;
            int right = nums.Length - 1;
            while (left < right)
            {
                int currentSum = nums[i] + nums[left] + nums[right];
                if (currentSum == target)
                {
                    return target;
                }

                if (Math.Abs(currentSum - target) < Math.Abs(closestSum - target))
                {
                    closestSum = currentSum;
                }

                if (currentSum < target)
                {
                    left++;
                }
                else
                {
                    right--;
                }
            }
        }
        return closestSum;
    }
}
// @lc code=end

